Huffman Coding

Huffman coding

It is a method for storing data using variable length codes try to obtain lossless compression data. This type of coding produces short codes for bits sequences that are frequent in the data, while long codes for bits sequences that rarely occur in the data. This algorithm was developed by David A. Huffman while he was a student at MIT in 1952.

Es un método para almacenar datos usando códigos de longitud variable para obtener compresión de datos sin pérdida. Este tipo de codificación produce códigos cortos para secuencias de bits que ocurren frecuentemente en los datos, mientras códigos largos para secuencias de bits que casi no ocurren. Este algoritmo fue desarrollado por David A. Huffman cuando el era un estudiante en el MIT en 1952.

Compression algorithm

It is based on the construction of a binary tree of nodes. A node can be an internal node or a leaf node (a node with no children). At the beginning of the algorithm, all nodes are leaf nodes. Each leaf node stores a symbol and the frequency of this symbol in the data. The algorithm uses a priority queue where the node with the lowest frequency is given the highest priority.

Compute the frequency of each symbol. Then create a leaf node for each symbol and add it to the priority queue.
While there are nodes in the queue: remove from the queue the two nodes with the highest frequency. Create an internal node with these two nodes as children and with a frequency equal to the sum of the frequency of the two children. Finally, add this new node to the priority queue.
The last node in the priority queue is the root node of the binary tree.

The example below illustrates how to use Huffman code to compress some text.

Este está basado en la construcción de un árbol binario de nodos. Un codo puede ser un nodo interno o un nodo terminal (un nodo que no tiene hijos). Al principio del algoritmo, todos los nodos son nodos terminales. Cada nodo terminal almacena un símbolo y la frecuencia del símbolo en los datos. El algoritmo usas una cola con prioridad en la cual el nodo con la menor frecuencia se le da la prioridad más alta.

Calcule la frecuencia de cada símbolo. Entonces cree un nodo terminal por cada símbolo y agréguelo a la cola de prioridad.
Mientras hay nodos en la cola: remueva de la cola los dos nodos con la más alta frecuencia. Cree un nodo interno con estos dos nodos como hijos y con una frecuencia igual a la suma de la de la frecuencia de los dos hijos. Finalmente, agregue este nodo a la cola con prioridad.
El último nodo en la cola con prioridad es el nodo raíz del árbol binario.

El ejemplo de abajo ilustra cómo usar los códigos de Huffman para comprimir un texto.

Problem 1

Create a dialog application called DavidHuffman using Wintempla. After creating the application create the shown GUI.

Cree una aplicación de Diálogo llamada DavidHuffman usando Wintempla. Después de crear el programa cree la GUI mostrada.

DavidHuffman.cpp

. . .
void DavidHuffman::btEncode_Click(Win::Event& e)
{
     wstring winput = tbxInput.Text;
     string input;
     Sys::Convert::WstringToString(winput, input);
     Sys::HuffmanCoder coder;
     coder.includeHuffmanCodesTable = false;
     string compressed;
     coder.Encode(input, compressed);
     string::iterator p;
     wchar_t text[256];
     for (p = compressed.begin(); p != compressed.end(); p++)
     {
          _snwprintf_s(text, 256, _TRUNCATE, L"%2X, ", (unsigned char)*p);
          tbxCompressed.Text += text;
     }
}

Problem 2

Create a dialog application called DavidAlbert using Wintempla. After creating the application create the shown GUI.

Cree una aplicación de Diálogo llamada DavidAlbert usando Wintempla. Después de crear el programa cree la GUI mostrada.

DavidAlbert.cpp

. . .
void DavidAlbert::btEncode_Click(Win::Event& e)
{
     //___________________________________________________________________ 1. Compress
     wstring winput = tbxInput.Text;
     string input;
     Sys::Convert::WstringToString(winput, input);
     Sys::HuffmanCoder coder;
     string compressed;
     coder.Encode(input, compressed);
     string::iterator p;
     wchar_t text[256];
     for (p = compressed.begin(); p != compressed.end(); p++)
     {
          _snwprintf_s(text, 256, _TRUNCATE, L"%2X, ", (unsigned char)*p);
          tbxCompressed.Text += text;
     }
     //___________________________________________________________________ 2. Uncompress
     string uncompressed;
     coder.Decode(compressed, uncompressed);
     //
     wstring wuncompressed;
     Sys::Convert::StringToWstring(uncompressed, wuncompressed);
     tbxUncompressed.Text = wuncompressed;
}

Problem 3

Create a dialog application called CompressDavid using Wintempla. After creating the application, open the Wikipedia page for Romeo and Juliet, then, save the source as Romeo_and_Juliet.htm in the project folder.

Cree una aplicación de Diálogo llamada CompressDavid usando Wintempla. Después de crear el programa, abra la página de Wikipedia de Romeo and Juliet, entonces, guarda la fuente cómo Rome_and_Juliet.htm en la carpeta del proyecto

CompressDavid.cpp

. . .
void CompressDavid::Window_Open(Win::Event& e)
{
     //_____________________________________________________ 1. Compress the data
     string input;
     Sys::FileAssistant::BinaryLoad(L"Romeo_and_Juliet.htm", input);
     Sys::HuffmanCoder coder;
     string compressed;
     coder.Encode(input, compressed);
     Sys::FileAssistant::BinarySave(L"Romeo_and_Juliet.txt", compressed);
     //_____________________________________________________ 2. Uncompress the data
     string uncompressed;
     coder.Decode(compressed, uncompressed);
     Sys::FileAssistant::BinarySave(L"Romeo_and_Juliet2.htm", uncompressed);
}

Huffman Coding

Huffman coding

Compression algorithm

© Copyright 2000-2021 Wintempla selo. All Rights Reserved. Jul 22 2021. Home